﻿using DataAnalyticsTools.Models;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataAnalyticsTools.Core
{
    /// <summary>
    /// 聚类分析器
    /// 提供K-means、层次聚类等多种聚类算法
    /// </summary>
    public static class ClusteringAnalyzer
    {
        /// <summary>
        /// K-means聚类算法
        /// 将样本划分为K个簇，使得簇内样本相似度最高
        /// </summary>
        /// <param name="data">特征矩阵，形状为[样本数, 特征数]</param>
        /// <param name="clusterCount">要形成的簇数量</param>
        /// <param name="maxIterations">最大迭代次数，默认100</param>
        /// <param name="randomSeed">随机种子，用于重现结果</param>
        /// <returns>聚类结果</returns>
        /// <example>
        /// 输入:
        ///   data = [[1, 1], [1, 2], [5, 5], [5, 6]]
        ///   clusterCount = 2
        /// 输出:
        ///   Labels = [0, 0, 1, 1]
        ///   Centroids = [[1, 1.5], [5, 5.5]]
        /// </example>
        public static ClusteringResult KMeans(
            float[][] data,
            int clusterCount,
            int maxIterations = 100,
            int? randomSeed = null)
        {
            if (data == null || data.Length == 0)
                return new ClusteringResult(Array.Empty<int>(), Array.Empty<float[]>());

            if (clusterCount < 1 || clusterCount > data.Length)
                throw new ArgumentException($"簇数量必须在1到{data.Length}之间");


            int featureCount = data[0].Length;
            var rng = randomSeed.HasValue ? new Random(randomSeed.Value) : new Random();

            // 初始化聚类中心
            var centroids = InitializeCentroids(data, clusterCount, rng);
            var labels = new int[data.Length];
            int iteration;

            for (iteration = 0; iteration < maxIterations; iteration++)
            {
                // 分配样本到最近的聚类中心
                bool changed = AssignLabels(data, centroids, labels);

                if (!changed)
                    break;

                // 更新聚类中心
                centroids = UpdateCentroids(data, labels, clusterCount);
            }

            // 计算轮廓系数
            var silhouetteScores = CalculateSilhouetteScores(data, labels);

            return new ClusteringResult(labels, centroids, silhouetteScores)
            {
                Algorithm = "KMeans",
                Iterations = iteration + 1,
                ConvergenceReached = iteration < maxIterations
            };
        }

        /// <summary>
        /// 层次聚类算法
        /// 自底向上合并最相似的簇，形成层次化的聚类结构
        /// </summary>
        /// <param name="data">特征矩阵，形状为[样本数, 特征数]</param>
        /// <param name="clusterCount">最终要形成的簇数量</param>
        /// <param name="linkageMethod">链接方法，默认使用平均链接</param>
        /// <returns>聚类结果</returns>
        /// <example>
        /// 输入:
        ///   data = [[1, 1], [1, 2], [5, 5], [5, 6], [10, 10]]
        ///   clusterCount = 3
        /// 输出:
        ///   Labels = [0, 0, 1, 1, 2]  // 形成3个自然簇
        /// </example>
        public static ClusteringResult HierarchicalClustering(
            float[][] data,
            int clusterCount,
            LinkageMethod linkageMethod = LinkageMethod.Average)
        {
            if (data == null || data.Length == 0)
                return new ClusteringResult(Array.Empty<int>(), Array.Empty<float[]>());

            if (clusterCount < 1 || clusterCount > data.Length)
                throw new ArgumentException($"簇数量必须在1到{data.Length}之间");

            int n = data.Length;

            // 初始化：每个样本作为一个聚类
            var clusters = Enumerable.Range(0, n)
                .Select(i => new List<int> { i })
                .ToList();

            // 计算原始样本的距离矩阵
            var sampleDistances = CalculateDistanceMatrix(data);

            // 使用字典存储簇间距离，key是"i,j"格式的字符串
            var clusterDistances = new Dictionary<string, float>();

            // 初始化簇间距离（每个样本是一个簇）
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    clusterDistances[$"{i},{j}"] = sampleDistances[i, j];
                }
            }

            var mergeHistory = new List<ClusterMerge>();

            // 持续合并直到达到目标簇数量
            while (clusters.Count > clusterCount)
            {
                // 找到距离最近的两个聚类
                var (minI, minJ, minDistance) = FindClosestClustersFixed(clusters.Count, clusterDistances);

                if (minI == -1 || minJ == -1)
                    break;

                mergeHistory.Add(new ClusterMerge(minI, minJ, minDistance, clusters.Count));

                // 更新簇间距离：计算新合并簇与其他簇的距离
                for (int k = 0; k < clusters.Count; k++)
                {
                    if (k == minI || k == minJ)
                        continue;

                    // 计算合并后的簇与簇k的距离
                    float newDistance = CalculateInterClusterDistanceFixed(
                        clusters[minI], clusters[minJ], clusters[k],
                        sampleDistances, linkageMethod);

                    // 更新距离字典
                    string key = minI < k ? $"{minI},{k}" : $"{k},{minI}";
                    clusterDistances[key] = newDistance;
                }

                // 删除与minJ相关的所有距离
                var keysToRemove = clusterDistances.Keys
                    .Where(k => k.StartsWith($"{minJ},") || k.EndsWith($",{minJ}"))
                    .ToList();
                foreach (var key in keysToRemove)
                {
                    clusterDistances.Remove(key);
                }

                // 合并聚类
                clusters[minI].AddRange(clusters[minJ]);
                clusters.RemoveAt(minJ);

                // 更新索引：所有大于minJ的簇索引减1
                var updatedDistances = new Dictionary<string, float>();
                foreach (var kvp in clusterDistances)
                {
                    var parts = kvp.Key.Split(',');
                    int i = int.Parse(parts[0]);
                    int j = int.Parse(parts[1]);

                    if (i > minJ) i--;
                    if (j > minJ) j--;

                    string newKey = i < j ? $"{i},{j}" : $"{j},{i}";
                    updatedDistances[newKey] = kvp.Value;
                }
                clusterDistances = updatedDistances;
            }

            // 分配标签和计算质心
            var labels = new int[n];
            var centroids = new float[clusters.Count][];

            for (int i = 0; i < clusters.Count; i++)
            {
                foreach (var index in clusters[i])
                {
                    labels[index] = i;
                }
                centroids[i] = CalculateClusterCentroid(data, clusters[i]);
            }

            var silhouetteScores = CalculateSilhouetteScores(data, labels);

            return new ClusteringResult(labels, centroids, silhouetteScores)
            {
                Algorithm = $"Hierarchical_{linkageMethod}",
                MergeHistory = mergeHistory
            };
        }

        /// <summary>
        /// DBSCAN聚类算法
        /// 基于密度的聚类，能发现任意形状的簇并识别噪声点
        /// </summary>
        /// <param name="data">特征矩阵</param>
        /// <param name="epsilon">邻域半径</param>
        /// <param name="minPoints">核心点所需的最小邻域点数</param>
        /// <returns>聚类结果，标签为-1表示噪声点</returns>
        /// <example>
        /// 输入:
        ///   data = [[1,1], [1,2], [2,1], [8,8], [8,9]]
        ///   epsilon = 1.5, minPoints = 2
        /// 输出:
        ///   Labels = [0, 0, 0, 1, 1]  // 两个密度相连的簇
        /// </example>
        public static ClusteringResult DBSCAN(float[][] data, float epsilon, int minPoints)
        {
            if (data == null || data.Length == 0)
                return new ClusteringResult(Array.Empty<int>(), Array.Empty<float[]>());

            int n = data.Length;
            var labels = new int[n];
            Array.Fill(labels, -1); // -1 表示未访问或噪声点

            int clusterId = 0;
            var visited = new bool[n];

            for (int i = 0; i < n; i++)
            {
                if (visited[i])
                    continue;

                visited[i] = true;
                var neighbors = FindNeighbors(data, i, epsilon);

                if (neighbors.Count < minPoints)
                {
                    labels[i] = -1; // 标记为噪声点
                }
                else
                {
                    ExpandCluster(data, labels, visited, i, neighbors, clusterId, epsilon, minPoints);
                    clusterId++;
                }
            }

            // 计算簇中心
            var centroids = CalculateDBCentroids(data, labels, clusterId);
            var silhouetteScores = CalculateSilhouetteScores(data, labels);

            return new ClusteringResult(labels, centroids, silhouetteScores)
            {
                Algorithm = "DBSCAN",
                NoisePoints = labels.Count(x => x == -1)
            };
        }

        /// <summary>
        /// 计算轮廓系数评估聚类质量
        /// 衡量样本与同簇样本的相似度和与其他簇样本的差异度
        /// </summary>
        /// <param name="data">特征矩阵，形状为[样本数, 特征数]</param>
        /// <param name="labels">聚类标签数组，长度等于样本数</param>
        /// <returns>
        /// 每个样本的轮廓系数数组，长度等于样本数，值域[-1, 1]
        /// 值越接近1表示聚类效果越好，负值表示可能被分错簇
        /// </returns>
        public static float[] CalculateSilhouetteScores(float[][] data, int[] labels)
        {
            if (data == null || data.Length == 0)
                return Array.Empty<float>();

            int n = data.Length;
            var scores = new float[n];
            var uniqueLabels = labels.Distinct().Where(l => l >= 0).ToArray(); // 排除噪声点

            if (uniqueLabels.Length <= 1)
            {
                Array.Fill(scores, 0f);
                return scores;
            }

            for (int i = 0; i < n; i++)
            {
                if (labels[i] == -1)
                {
                    scores[i] = -1f; // 噪声点的轮廓系数为-1
                    continue;
                }

                var currentLabel = labels[i];
                var sameCluster = new List<float[]>();
                var otherClusters = new Dictionary<int, List<float[]>>();

                // 分组数据
                for (int j = 0; j < n; j++)
                {
                    if (i == j) continue;

                    if (labels[j] == currentLabel)
                    {
                        sameCluster.Add(data[j]);
                    }
                    else if (labels[j] != -1) // 排除噪声点
                    {
                        if (!otherClusters.ContainsKey(labels[j]))
                            otherClusters[labels[j]] = new List<float[]>();
                        otherClusters[labels[j]].Add(data[j]);
                    }
                }

                // 计算样本i到同簇其他样本的平均距离
                float a = sameCluster.Count > 0 ?
                    sameCluster.Average(other => MathHelper.EuclideanDistance(data[i], other)) : 0;

                // 计算样本i到其他簇的最小平均距离
                float b = otherClusters.Count > 0 ?
                    otherClusters.Min(pair => pair.Value.Average(other => MathHelper.EuclideanDistance(data[i], other))) : float.MaxValue;

                if (Math.Max(a, b) > 0)
                    scores[i] = (b - a) / Math.Max(a, b);
                else
                    scores[i] = 0;
            }

            return scores;
        }

        #region K-means 辅助方法

        private static float[][] InitializeCentroids(float[][] data, int clusterCount, Random rng)
        {
            var centroids = new float[clusterCount][];
            var indices = Enumerable.Range(0, data.Length).OrderBy(x => rng.Next()).Take(clusterCount).ToArray();

            for (int i = 0; i < clusterCount; i++)
            {
                centroids[i] = data[indices[i]].ToArray();
            }

            return centroids;
        }

        private static bool AssignLabels(float[][] data, float[][] centroids, int[] labels)
        {
            bool changed = false;

            for (int i = 0; i < data.Length; i++)
            {
                var distances = centroids.Select(c => MathHelper.EuclideanDistance(data[i], c)).ToArray();
                var newLabel = Array.IndexOf(distances, distances.Min());

                if (newLabel != labels[i])
                {
                    labels[i] = newLabel;
                    changed = true;
                }
            }

            return changed;
        }

        private static float[][] UpdateCentroids(float[][] data, int[] labels, int clusterCount)
        {
            var centroids = new float[clusterCount][];
            var featureCount = data[0].Length;

            for (int k = 0; k < clusterCount; k++)
            {
                var clusterData = data.Where((_, i) => labels[i] == k).ToArray();
                if (clusterData.Length == 0)
                {
                    // 如果簇为空，随机重新初始化
                    centroids[k] = new float[featureCount];
                    var rng = new Random();
                    for (int j = 0; j < featureCount; j++)
                    {
                        var column = data.Select(row => row[j]).ToArray();
                        centroids[k][j] = (float)(rng.NextDouble() * (column.Max() - column.Min()) + column.Min());
                    }
                    continue;
                }

                centroids[k] = new float[featureCount];
                for (int j = 0; j < featureCount; j++)
                {
                    centroids[k][j] = clusterData.Average(row => row[j]);
                }
            }

            return centroids;
        }

        #endregion

        #region 层次聚类辅助方法

        private static float[,] CalculateDistanceMatrix(float[][] data)
        {
            int n = data.Length;
            var distances = new float[n, n];

            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    var dist = MathHelper.EuclideanDistance(data[i], data[j]);
                    distances[i, j] = distances[j, i] = dist;
                }
            }

            return distances;
        }

        private static (int i, int j, float distance) FindClosestClustersFixed(
    int clusterCount, Dictionary<string, float> distances)
        {
            float minDistance = float.MaxValue;
            int minI = -1, minJ = -1;

            foreach (var kvp in distances)
            {
                if (kvp.Value < minDistance)
                {
                    minDistance = kvp.Value;
                    var parts = kvp.Key.Split(',');
                    minI = int.Parse(parts[0]);
                    minJ = int.Parse(parts[1]);
                }
            }

            return (minI, minJ, minDistance);
        }

        private static float CalculateInterClusterDistanceFixed(
            List<int> clusterA,
            List<int> clusterB,
            List<int> clusterC,
            float[,] sampleDistances,
            LinkageMethod method)
        {
            // 合并clusterA和clusterB后，计算与clusterC的距离
            var mergedCluster = new List<int>(clusterA);
            mergedCluster.AddRange(clusterB);

            return method switch
            {
                LinkageMethod.Single => CalculateSingleLinkageFixed(mergedCluster, clusterC, sampleDistances),
                LinkageMethod.Complete => CalculateCompleteLinkageFixed(mergedCluster, clusterC, sampleDistances),
                LinkageMethod.Average => CalculateAverageLinkageFixed(mergedCluster, clusterC, sampleDistances),
                _ => CalculateAverageLinkageFixed(mergedCluster, clusterC, sampleDistances)
            };
        }

        private static float CalculateSingleLinkageFixed(
            List<int> clusterA, List<int> clusterB, float[,] distances)
        {
            float minDistance = float.MaxValue;

            foreach (var sampleA in clusterA)
            {
                foreach (var sampleB in clusterB)
                {
                    var distance = distances[sampleA, sampleB];
                    if (distance < minDistance)
                        minDistance = distance;
                }
            }

            return minDistance;
        }

        private static float CalculateCompleteLinkageFixed(
            List<int> clusterA, List<int> clusterB, float[,] distances)
        {
            float maxDistance = 0f;

            foreach (var sampleA in clusterA)
            {
                foreach (var sampleB in clusterB)
                {
                    var distance = distances[sampleA, sampleB];
                    if (distance > maxDistance)
                        maxDistance = distance;
                }
            }

            return maxDistance;
        }

        private static float CalculateAverageLinkageFixed(
            List<int> clusterA, List<int> clusterB, float[,] distances)
        {
            float totalDistance = 0f;
            int pairCount = 0;

            foreach (var sampleA in clusterA)
            {
                foreach (var sampleB in clusterB)
                {
                    totalDistance += distances[sampleA, sampleB];
                    pairCount++;
                }
            }

            return pairCount > 0 ? totalDistance / pairCount : float.MaxValue;
        }

        private static float[] CalculateClusterCentroid(float[][] data, List<int> clusterIndices)
        {
            if (clusterIndices.Count == 0)
                return Array.Empty<float>();

            int featureCount = data[0].Length;
            var centroid = new float[featureCount];

            for (int j = 0; j < featureCount; j++)
            {
                centroid[j] = clusterIndices.Average(i => data[i][j]);
            }

            return centroid;
        }

        #endregion

        #region DBSCAN 辅助方法

        private static List<int> FindNeighbors(float[][] data, int pointIndex, float epsilon)
        {
            var neighbors = new List<int>();

            for (int i = 0; i < data.Length; i++)
            {
                if (i == pointIndex) continue;

                if (MathHelper.EuclideanDistance(data[pointIndex], data[i]) <= epsilon)
                {
                    neighbors.Add(i);
                }
            }

            return neighbors;
        }

        private static void ExpandCluster(
            float[][] data,
            int[] labels,
            bool[] visited,
            int pointIndex,
            List<int> neighbors,
            int clusterId,
            float epsilon,
            int minPoints)
        {
            labels[pointIndex] = clusterId;
            var processedNeighbors = new HashSet<int>(neighbors);

            for (int i = 0; i < neighbors.Count; i++)
            {
                int neighborIndex = neighbors[i];

                if (!visited[neighborIndex])
                {
                    visited[neighborIndex] = true;
                    var newNeighbors = FindNeighbors(data, neighborIndex, epsilon);

                    if (newNeighbors.Count >= minPoints)
                    {
                        // 只添加未处理的邻居
                        foreach (var nn in newNeighbors)
                        {
                            if (!processedNeighbors.Contains(nn))
                            {
                                neighbors.Add(nn);
                                processedNeighbors.Add(nn);
                            }
                        }
                    }
                }

                if (labels[neighborIndex] == -1)
                {
                    labels[neighborIndex] = clusterId;
                }
            }
        }

        private static float[][] CalculateDBCentroids(float[][] data, int[] labels, int clusterCount)
        {
            var centroids = new float[clusterCount][];

            for (int i = 0; i < clusterCount; i++)
            {
                var clusterData = new List<float[]>();
                for (int j = 0; j < data.Length; j++)
                {
                    if (labels[j] == i)
                    {
                        clusterData.Add(data[j]);
                    }
                }

                if (clusterData.Count > 0)
                {
                    int featureCount = data[0].Length;
                    centroids[i] = new float[featureCount];
                    for (int k = 0; k < featureCount; k++)
                    {
                        centroids[i][k] = clusterData.Average(x => x[k]);
                    }
                }
                else
                {
                    centroids[i] = new float[data[0].Length];
                }
            }

            return centroids;
        }

        #endregion
    }
}
